package com.zjsru.plan2023.oneday;

import com.zjsru.leetcode75.level1.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * @Author: cookLee
 * @Date: 2023-12-15
 * 反转二叉树的奇数层
 */
public class ReverseOddLevels {

    /**
     * 主
     * \
     * 输入：root = [2,3,5,8,13,21,34]
     * 输出：[2,5,3,8,13,21,34]
     * 解释：
     * 这棵树只有一个奇数层。
     * 在第 1 层的节点分别是 3、5 ，反转后为 5、3 。
     * \
     * 输入：root = [7,13,11]
     * 输出：[7,11,13]
     * 解释：
     * 在第 1 层的节点分别是 13、11 ，反转后为 11、13 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(2, new TreeNode(3, new TreeNode(8), new TreeNode(13)), new TreeNode(5, new TreeNode(21), new TreeNode(43)));
        ReverseOddLevels reverseOddLevels = new ReverseOddLevels();
        System.out.println(reverseOddLevels.reverseOddLevels(tree));
    }

    /**
     * 广度优先搜索+双指针
     *
     * @param root 根
     * @return {@link TreeNode}
     */
    public TreeNode reverseOddLevels(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        //判断是否是奇数层，从0开始故展示false
        boolean odd = false;
        while (!queue.isEmpty()) {
            int len = queue.size();
            List<TreeNode> list = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                TreeNode treeNode = queue.poll();
                if (odd) {
                    list.add(treeNode);
                }
                //因为是完美二叉树，这一步只要判断左节点相当于判断下一层是否有节点即可
                if (treeNode.left != null) {
                    //偶数层放入队列
                    queue.add(treeNode.left);
                    queue.add(treeNode.right);
                }
            }
            //如果是奇数层，使用双指针掉转节点方向
            if (odd) {
                this.helper(len, list);
            }
            //转化
            odd ^= true;
        }
        return root;
    }

    /**
     * 反转数字实现助手类
     *
     * @param len  len
     * @param list 列表
     */
    private void helper(Integer len, List<TreeNode> list) {
        for (int left = 0, right = len - 1; left < right; left++, right--) {
            int temp = list.get(left).val;
            list.get(left).val = list.get(right).val;
            list.get(right).val = temp;
        }
    }
}
